package leetcode.biweekly.week95;

import leetcode.helper.H;

//Solution4Test
public class Solution4 {

	public long maxPower(int[] stations, int r, int k) {
		int len = stations.length;
		this.n = len + 2;
		long[] sums = new long[n];
		for (int i = 0; i < len; i++) {
			add(sums, i, stations[i]);
		}
		long max = -1;
		for (int i = 0; i < len; i++) {
			int LL = i - r - 1, RR = i + r;
			long suml = LL < 0 ? 0 : query(sums, LL);
			long sumr = RR >= len ? query(sums, len - 1) : query(sums, RR);
			max = Math.max(sumr - suml, max);
		}
		long ans = 0l;
		long L = 0, R = max + k + 1;
		while (L <= R) {
			long m = ((R - L) >> 1) + L;
			long cur = k;
			long[] s = sums.clone();
			for (int i = 0; i < len && cur >= 0; i++) {
				int LL = i - r - 1, RR = i + r;
				long suml = LL < 0 ? 0 : query(s, LL);
				long sumr = RR >= len ? query(s, len - 1) : query(s, RR);
				if (sumr - suml < m) {
					long diff = m - (sumr - suml);
					if (RR >= len) {
						add(s, len - 1, diff);
					} else {
						add(s, RR, diff);
					}
					cur -= diff;
				}
			}
			if (cur >= 0) {
				ans = m;
				L = m + 1;
			} else {
				R = m - 1;
			}
		}
		return ans;
	}

	int n;

	public void add(long[] sums, int num, long add) {
		num += 1;
		while (num < n) {
			sums[num] += add;
			num += this.lowbit(num);
		}
	}

	public long query(long[] sums, int num) {
		long ans = 0;
		num += 1;
		while (num > 0) {
			ans += sums[num];
			num -= this.lowbit(num);
		}
		return ans;
	}


	public int lowbit(int num) {
		return num & -num;
	}

}
